package j2024.j202411;

import java.util.ArrayList;
import java.util.List;

public class j1112 {
    /**
     * 17. 电话号码的字母组合
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     *
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     */
        String[] phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        StringBuilder path;
        List<StringBuilder> ret;
        public List<StringBuilder> letterCombinations(String digits) {
            path = new StringBuilder();
            ret = new ArrayList<StringBuilder>();
            if(digits.length() == 0){
                return ret;
            }
            dfs(digits,0);
            return ret;
        }
        public void dfs(String digits,int pos){
            if(pos == digits.length()){
                ret.add(path);
                return;
            }
            String tmp = phone[digits.charAt(pos)-'0'];
            for (int i = 0; i <tmp.length(); i++) {
                path.append(tmp.charAt(i));
                dfs(digits,pos + 1);
                path.deleteCharAt(path.length()-1);
            }
        }


    /**
     * 77. 组合
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     *
     * 你可以按 任何顺序 返回答案。
     * @param n
     * @param k
     * @return
     */
    List<List<Integer>> Ret;
    List<Integer> Path;
    int newn,newk;
    public List<List<Integer>> combine(int n, int k) {
        Ret = new ArrayList<>();
        Path = new ArrayList<>();
        newn = n;newk = k;
        Dfs(1);
        return Ret;
    }
    public void Dfs(int s){
        if(Path.size()==newk){
            Ret.add(new ArrayList<>(Path));
        }
        for (int i = s; i <= newn; i++) {
            Path.add(i);
            Dfs(i+1);
            Path.remove(Path.size()-1);
        }
    }


    /**
     * 46. 全排列
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     * @param nums
     * @return
     */
    List<List<Integer>> RET;
    List<Integer> PATH;
    boolean[] isvis;
    public List<List<Integer>> permute(int[] nums) {
        RET = new ArrayList<>();
        PATH = new ArrayList<>();
        isvis = new boolean[nums.length];
        check(nums);
        return RET;
    }
    public void check(int[] nums){
        if(PATH.size()==nums.length){
            RET.add(new ArrayList<>(PATH));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(!isvis[i]){
                isvis[i] = true;
                PATH.add(nums[i]);
                check(nums);
                isvis[i] = false;
                PATH.remove(PATH.size()-1);
            }
        }
    }


}
